-module(chapter3).

-compile(export_all).

%%3-1
sum(N) when N>0 ->
    N + sum(N-1);
sum(0) ->
    0.

sum2(0) ->
    0;
sum2(N) ->
    N + sum2(N-1).

sum(N, M) when N==M ->
    M;
sum(N, M) when N<M ->
    N + sum(N+1, M).

factorial(0) ->
    1;
factorial(N) ->
    N * factorial(N-1).

factorial2(0) ->
    1;
factorial2(N) when N>0 ->
    N * factorial(N-1).

%% end 3-1

%% 3-2
create(N) when N>0 ->
    create(N, [1]).

create(1, List) ->
    List;
create(N, [H|T]) ->
    create(N-1, [H|[N|T]]).


reverse_create(N) when N>0 ->
    reverse_create(N, [N]).

reverse_create(1, List) ->
    List;
reverse_create(N, [H|T]) ->
    reverse_create(N-1, [H|[H-N+1|T]]).

%% end 3-2

%% 3-3

print(N) when N>0 ->
    % [io:format("Number:~p~n", [X]) || X <- chapter3:create(N)].
    print(N, [1]).
print(1, List) ->
    List,
    io:format("Number:~p~n", [1]);
print(N, [H|T]) ->
    print(N-1, [H|[N|T]]),
    io:format("Number:~p~n", [N]).

print_even(N) when N>0 ->
    print_even(N, [2]).

print_even(2, List) ->
    List,
    io:format("Number:~p~n", [2]);
print_even(N, [H|T]) when N rem 2==0 ->
    print_even(N-1, [H|[N|T]]),
    io:format("Number:~p~n", [N]);
print_even(N, List) ->
    print_even(N-1, List).
%% end 3-3

%% 3-4 参考 db.erl

%% 3-5
filter([], _) ->
    [];
filter(List, N) when is_list(List), is_integer(N) ->
    [H|T] = List,
    if
        H=<N ->
            [H|filter(T, N)];
        true ->
            filter(T, N)
    end.

reverse([]) ->
    [];
reverse(List) ->
    reverse(List, []).

reverse([], List) ->
    List;
reverse(List, List2) ->
    [H|T] = List,
    reverse(T, [H|List2]).

concatenate([]) ->
    [];
concatenate(List) ->
    concatenate(List, []).

concatenate([], List) ->
    reverse(List);
concatenate(List, List2) ->
    [Head|Tail] = List,
    concatenate(Tail, concatenate_plus(List2, Head)).

concatenate_plus([],[]) ->
    [];
concatenate_plus([], List) ->
    reverse(List);
concatenate_plus(List, []) ->
    List;
concatenate_plus(List, List2) ->
    [H|Tail] = List,
    concatenate_plus(Tail, [H|List2]).

flatten([]) ->
    [];
flatten(List) ->
    [H|T] = List,
    if
        is_list(H), is_list(T) ->
            concatenate_plus(flatten(T), flatten(H));
        is_list(H) ->
            [T|flatten(H)];
        is_list(T) ->
            concatenate_plus([H], flatten(T))
    end.

%% end 3-5

%% 3-6
quicksort([]) ->
    [];
quicksort([H|Tail]) ->
    quicksort(Tail, H, [], []).

quicksort([], A, Smaller, Bigger) ->
    quicksort(Smaller)++[A]++quicksort(Bigger);
quicksort([H|Tail], A, Smaller, Bigger) when H>=A ->
    quicksort(Tail, A, Smaller, [H|Bigger]);
quicksort([H|Tail], A, Smaller, Bigger) ->
    quicksort(Tail, A, [H|Smaller], Bigger).



mergesort([]) ->
    [];
mergesort([T]) ->
    [T];
mergesort(List) ->
    {Left, Right} = lists:split(length(List) div 2, List),
    mergesort(mergesort(Left), mergesort(Right)).

mergesort(Left, Right) ->
    mergesort(Left, Right, []).

mergesort([], [], List) ->
    List;
mergesort([], Right, List) ->
    List++Right;
mergesort(Left, [], List) ->
    List++Left;
mergesort([LHead|LTail], [RHead|_RTail]=Right, List) when LHead<RHead ->
    mergesort(LTail, Right, List++[LHead]);
mergesort(Left, [RHead|RTail], List) ->
    mergesort(Left, RTail, List++[RHead]).




%% end 3-6
